package solutions.leetcode.easy;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/shortest-completing-word/">748. 最短补全词</a>
 */
public class Solution748 extends BaseSolution {

    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] origin = getCount(licensePlate);
        String rst = null;
        for (String word : words) {
            int[] now = getCount(word);
            boolean ok = true;
            for (int i = 0; i < 26; i++) {
                if (now[i] < origin[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                rst = rst == null || rst.length() > word.length() ? word : rst;
            }
        }
        return rst;
    }

    private int[] getCount(String s) {
        int[] count = new int[26];
        for (char c : s.toLowerCase().toCharArray()) {
            if (c >= 'a' && c <= 'z') {
                count[c - 'a']++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution748 solution = new Solution748();
    }
}